A constraint solver is generally understood as a process, or a processor adapted to execute a process, that accepts as input a system of constraints including one or more constraints over one or more variables, and returns an assignment of values to those variables, if one exists, such that all of the constraints are satisfied. If no such assignment of variables exists, the process determines that the constraint system is unsatisfiable, i.e., the process determines that there is no set of values that can be assigned to the variables such that all constraints are satisfied. In general, “solving” a constraint problem includes either determining whether a constraint-satisfying assignment exists, or finding such an assignment, or both.
The set of possible assignments, i.e., the several combinations of values that can be assigned to the constraint system variables, generally describes a search space over which the constraint solver process/algorithm executes. If the number of constraint variables and/or the number of constraints in the constraint system are large, the theoretical search space, i.e., the set of each and every combination of values that can be assigned to all the variables, can become very large. Such a constraint problem may be intractable, i.e., even a large computer or a number solvers operating together may not be able to solve the problem in a reasonable time (e.g., minutes, hours, or even days), and/or may run out of memory while solving the problem.
A typical constraint solver includes several adjustable parameters. Generally, one or more of these parameters can be tuned or adjusted to affect the manner (e.g., order) in which the solver/algorithm searches the space of possible assignments. Thus, by appropriately selecting the parameter values, the overall search space can be explored efficiently in order to find a solution. A choice of values for the parameters of a solver is commonly referred to as a configuration for the constraint solver.
An ensemble of constraint solvers includes several constraint-solver instances (nodes), running concurrently, attempting to find a satisfying assignment to a specified system of constraints. All of the constraint solvers in the ensemble may terminate once any of the solvers either finds a satisfying assignment to the variables of the constraint system or determines that the constraint problem is unsatisfiable. The coordinated start and termination of the ensemble solvers can be handled by a designated master process. An ensemble can include as few as two solvers, but typically includes a large number of solvers, e.g., 100 or 1000 solvers.
Generally, the solvers in the ensemble are either different algorithms accepting the same input, or differently configured versions of the same algorithm. The individual constraint solvers that form an ensemble may or may not share information with each other, e.g., about an area of the search space that a solver has already explored. Whether or not such information is shared, if different solvers simultaneously search different areas of the overall search space corresponding to a problem to be solved, an ensemble can operate faster than a single constraint solver configured to solved that problem. The different solvers can be adapted by assigning different configurations thereto such that one or more corresponding parameters of different solvers are assigned different values. The solvers thus configured can search different areas of the overall search space in different orders so that at least one of the solvers may explore the area that includes a solution to the problem relatively early. Thus the ensemble may find the solution faster than a single solver. This performance benefit can diminish, however, if one or more solvers initially explore search areas in which the solution is unlikely to be found or if several solvers explore the search space in substantially the same manner. As such, some techniques that can be used to configure only a single solver are not useful in configuring an ensemble of solvers such that the overall search space can be explored in an efficient manner.
Therefore, there is a need for a system and/or method that can configure a number of solvers in an ensemble according to a constraint problem to be solved. There is also a need to be able to readjust the configurations for one or more solvers in the ensemble as the solvers attempt to find the solution, such that the likelihood of finding a solution may be increased and/or the time required to find the solution may be decreased.